package com.jinan.algorithm.slidingWindow;

import java.util.ArrayList;
import java.util.List;

public class KMPtest {

    public static void main(String[] args) {
        String text = "BBC ABCDABD ABCDABCDABDE";
        String pattern = "ABCDABD";
        int[] next = computeNext(pattern);
        kmpSearch(text, pattern, next);
    }

    /**
     * 计算字符串模式的next数组。
     * next数组用于KMP算法中，指示在模式字符串中出现字符失配时，应向前移动多少位。
     *
     * @param pattern 模式字符串
     * @return next数组
     */
    public static int[] computeNext(String pattern) {
        // 初始化next数组与长度相等
        int[] next = new int[pattern.length()];
        // 初始化变量j，用于next数组的构建
        int j = 0;

        // 遍历模式字符串，从第二个字符开始
        for (int i = 1; i < pattern.length(); i++) {
            // 当前字符与j位置的字符不匹配，且j大于0，回退j到next[j-1]
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            // 如果当前字符与j位置的字符匹配，j自增
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            // 更新next数组的值
            next[i] = j;
        }
        // 打印next数组，用于调试
        for (int i : next) {
            System.out.print(i + " ");
        }
        // 换行，格式化输出
        System.out.println();
        // 返回计算完成的next数组
        return next;
    }

    /**
     * 使用KMP算法在文本中搜索模式。
     * KMP算法通过使用next数组优化了字符串匹配过程，避免了不必要的字符比较。
     *
     * @param text    文本字符串
     * @param pattern 模式字符串
     * @param next    模式字符串的next数组
     */
    public static void kmpSearch(String text, String pattern, int[] next) {
        // 初始化列表存储匹配位置
        List<Integer> positions = new ArrayList<>();

        // 初始化文本与模式的指针
        int i = 0, j = 0;

        // 遍历文本字符串，直到文本或模式结束
        while (i < text.length() && j < pattern.length()) {

            // 当前字符不匹配，且j大于0，回退j到next[j-1]
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }

            // 如果当前字符匹配，i和j都自增
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {//首次不匹配
                i++; // 只增加文本指针
            }

            // 检查是否找到完整的模式串
            if (j == pattern.length()) {
                // 添加模式的起始位置
                positions.add(i - j);
                // 重置j，继续搜索下一个可能的模式
                j = next[j - 1];
            }
        }

        // 判断是否找到模式
        if (!positions.isEmpty()) {
            System.out.println("Pattern found at indices: " + positions);
        } else {
            System.out.println("Pattern not found.");
        }
    }


}
